package gold.digger;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC306 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public boolean isAdditiveNumber(String num) {
            return backtracking(num, 0, new ArrayList<>());
        }

        private boolean backtracking(String num, int pos, List<String> nums) {
            if (pos == num.length())
                return nums.size() >= 3;

            String n = "";
            for (int i = pos; i < num.length(); ++i) {
                n = num.substring(pos, i + 1);
                // pruning 剪枝...
                if (nums.size() >= 2 &&
                        new BigInteger(nums.get(nums.size() - 2))
                                .add(new BigInteger(nums.get(nums.size() - 1))).compareTo(new BigInteger(n)) < 0) {
                    return false;
                }

                if (nums.size() < 2 ||
                        new BigInteger(nums.get(nums.size() - 2))
                                .add(new BigInteger(nums.get(nums.size() - 1))).toString().equals(n)) {
                    nums.add(n);
                    if (backtracking(num, i + 1, nums)) return true;
                    nums.remove(nums.size() - 1); // backtracking 招牌动作 ...
                }
                // process leading zeroes
                if (num.charAt(pos) == '0') return false;
            }

            return false;
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.isAdditiveNumber(null));
    }

    public static void main(String[] args) throws Exception {
        LC306 an = new LC306();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
